//
// Created by Administrator on 2024/6/14.
//
#include "stdio.h"
#include <bits/stdc++.h>

using namespace std;

/**
 * 贪心算法GreedySelector:
 *    若区间[si, fi)与区间[sj, fj)不相交，则称活动i与j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与j相容
 * @param n
 * @param s 起始时间
 * @param f 结束时间
 * @param A 是否为最大相容集合子集
 */
void GS (int n, int s[], int f[], bool A[])
{   A[1] = true;
    int j = 1;
    for (int i = 2; i <= n; ++i) {
        if(s[i] >= f[j]) {
            A[i] = true;
            j = i;
        } else {
            A[i] = false;
        }
    }
}

int main(){
    int n = 12;
    int s[] = {0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
    int f[] = {0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
    bool A[] = {0, 1};
    GS(n, s, f, A);
    for(int i = 1; i <= n; i++){
        if(A[i])
            cout<<i<<" ";
    }

    return 0;
}